package q144_preorderTraversal;

import CommonClass.Common;
import CommonClass.Common.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
public class Solution_3 {
    public List<Integer> preorderTraversal(Common.TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);

        // 通过栈的方式来前序遍历整颗树
        // 这里需要注意的是压入栈的顺序，由于栈是先进后出
        // 所以我们采用的方式是先压入右边节点，然后再压入左边节点，这样才能够保证中 左 右的顺序
        while (!stack.isEmpty()){
            // 弹出最上方的节点
            TreeNode node = stack.pop();
            // 加入中节点
            res.add(node.val);
            // 压入右节点
            if (node.right != null) {
                stack.push(node.right);
            }
            // 压入左节点
            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return res;

    }
}
